/*
 * (C) Copyright 2014-2016, by Dimitrios Michail
 *
 * JHeaps Library
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.jheaps

/**
 * A heap whose elements can be addressed using handles.
 *
 * An insert operation returns a [AddressableHeap.Handle] which can later
 * be used in order to manipulate the element, such as decreasing its key, or
 * deleting it. Storing the handle externally is the responsibility of the user.
 *
 * @param <K>
 * the type of keys maintained by this heap
 * @param <V>
 * the type of values maintained by this heap
 *
 * @author Dimitrios Michail
</V></K> */
interface AddressableHeap<K, V> {
    /**
     * A heap element handle. Allows someone to address an element already in a
     * heap and perform additional operations.
     *
     * @param <K>
     * the type of keys maintained by this heap
     * @param <V>
     * the type of values maintained by this heap
    </V></K> */
    interface Handle<K, V> {
        /**
         * Return the key of the element.
         *
         * @return the key of the element
         */

        val key: K

        /**
         * Return the value of the element.
         *
         * @return the value of the element
         */
        /**
         * Set the value of the element.
         *
         * @param value
         * the new value
         */

        var value: V?

        /**
         * Decrease the key of the element.
         *
         * @param newKey
         * the new key
         * @throws IllegalArgumentException
         * if the new key is larger than the old key according to
         * the comparator used when constructing the heap or the
         * natural ordering of the elements if no comparator was
         * used
         */
        fun decreaseKey(newKey: K)

        /**
         * Delete the element from the heap that it belongs.
         *
         * @throws IllegalArgumentException
         * in case this function is called twice on the same element
         * or the element has already been deleted using
         * [AddressableHeap.deleteMin].
         */
        fun delete()
    }

    /**
     * Returns the comparator used to order the keys in this AddressableHeap, or
     * `null` if this heap uses the [natural][Comparable] of its keys.
     *
     * @return the comparator used to order the keys in this heap, or
     * `null` if this addressable heap uses the natural ordering
     * of its keys
     */
    fun comparator(): Comparator<in K?>?

    /**
     * Insert a new element into the heap.
     *
     * @param key
     * the element's key
     * @param value
     * the element's value
     *
     * @return a handle for the newly added element
     */
    fun insert(key: K, value: V?): Handle<K, V>

    /**
     * Insert a new element into the heap with a null value.
     *
     * @param key
     * the element's key
     * @return a handle for the newly added element
     */
    fun insert(key: K): Handle<K, V> = insert(key,null)

    /**
     * Find an element with the minimum key.
     *
     * @return a handle to an element with minimum key
     */
    fun findMin(): Handle<K, V>

    /**
     * Delete and return an element with the minimum key. If multiple such
     * elements exists, only one of them will be deleted. After the element is
     * deleted the handle is invalidated and only method [Handle.getKey]
     * and [Handle.getValue] can be used.
     *
     * @return a handle to the deleted element with minimum key
     */
    fun deleteMin(): Handle<K, V>

    /**
     * Returns `true` if this heap is empty.
     *
     * @return `true` if this heap is empty, `false` otherwise
     */
    val isEmpty: Boolean

    /**
     * Returns the number of elements in the heap.
     *
     * @return the number of elements in the heap
     */
    fun size(): Long

    /**
     * Clear all the elements of the heap. After calling this method all handles
     * should be considered invalidated and the behavior of methods
     * [Handle.decreaseKey] and [Handle.delete] is
     * undefined.
     */
    fun clear()
}
